package com.camus.datastructureandalgorithm.algorithm.sort;

import java.util.Random;

/**
 * @author jie.deng 快速排序
 */
public class QuickSortArray implements SortArray {

    @Override
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }

        // 原地排序
        sortArray(nums, 0, nums.length - 1);

        return nums;
    }

    private void sortArray(int[] nums, int lIdx, int rIdx) {
        // 递推公式: quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r)
        // 终止条件: p>=r
        if (lIdx >= rIdx) {
            return;
        }

        // 获取分区点
        int q = partition(nums, lIdx, rIdx);
        sortArray(nums, lIdx, q - 1);
        sortArray(nums, q + 1, rIdx);
    }

    private int partition(int[] nums, int lIdx, int rIdx) {
        // 选择基准
        int pivotIdx = choosePivot(nums, lIdx, rIdx);
        int pivot = nums[pivotIdx];
        
        // 索引emptyIdx为空位，可覆盖
        int emptyIdx = pivotIdx;
        // 索引r后面的元素都大于pivot
        int r = rIdx;
        // 索引l前面的元素都小于等于pivot
        int l = lIdx;

        while (r > l) {
        	// 注意：先从后往前，再从前往后。
        	// 从后往前，找第一个不满足条件的元素
            while (nums[r] > pivot && r > l) {
                r--;
            }
            if (r > l) {
                nums[emptyIdx] = nums[r];
                emptyIdx = r;
            }
            
        	// 从前往后，找第一个不满足条件的元素            
            while (nums[l] <= pivot && r > l) {
                l++;
            }
            if (r > l) {
                nums[emptyIdx] = nums[l];
                emptyIdx = l;
            }
        }

        nums[emptyIdx] = pivot;
        return emptyIdx;
    }

    private int choosePivot(int[] nums, int lIdx, int rIdx) {
        return new Random().nextInt(rIdx - lIdx) + lIdx;

//        return lIdx;

//        return rIdx;

        // 取nums[lIdx]、nums[rIdx]、nums[(lIdx+rIdx)/2]这3个数中的中位数
//        if (lIdx >= rIdx) {
//            return lIdx;
//        }
//        int midIdx = (lIdx + rIdx) / 2;
//        int[] arr = new int[]{lIdx, midIdx, rIdx};
//        for (int i = 0; i < arr.length - 1; i++) {
//            int min = nums[arr[i]];
//            int minIdx = i;
//            for (int j = i + 1; j < arr.length; j++) {
//                if (nums[arr[j]] < min) {
//                    min = nums[arr[j]];
//                    minIdx = j;
//                }
//            }
//            if (minIdx != i) {
//                arr[i] = arr[i] ^ arr[minIdx];
//                arr[minIdx] = arr[i] ^ arr[minIdx];
//                arr[i] = arr[i] ^ arr[minIdx];
//            }
//        }
//        return arr[1];
    }

}
